#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        int h = board.size(), w = board[0].size();
        vector<vector<bool>> visited(h, vector<bool>(w));
        for (int i = 0; i < h; ++i)
        {
            for (int j = 0; j < w; ++j)
            {
                bool flag = check(board, visited, i, j, word, 0);
                if (flag) return true;
            }
        }
        return false;
    }

    bool check(vector<vector<char>>& board, vector<vector<bool>>& visited, int i, int j, string s, int k)
    {
        if (board[i][j] != s[k]) return false;
        if (k == s.size() - 1) return true;
        visited[i][j] = true;
        int dics[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
        bool res = false;
        for (auto dir : dics)
        {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.size() && newj >= 0 && j < board[0].size())
            {
                if (!visited[newi][newj])
                {
                    bool flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag)
                    {
                        res = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return res;
    }

    int minimumTotal(vector<vector<int>>& triangle) {
        int m = triangle.size();
        vector<vector<int>> dp(m);
        for (int i = 0; i < m; ++i)
            dp[i].resize(i + 1);
        dp[0][0] = triangle[0][0];
        for (int i = 1; i < m; ++i)
        {
            for (int j = 0; j <= i; ++j)
            {
                if (j > 0 && j < i) dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle[i][j];
                else if (j == i) dp[i][j] = dp[i - 1][j - 1] + triangle[i][j];
                else dp[i][j] = dp[i - 1][j] + triangle[i][j];
            }
        }
        int res = INT_MAX;
        for (int i = 0; i < m; ++i)
            res = min(res, dp[m - 1][i]);
        return res;
    }

    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (j > 0) dp[j] = min(dp[j], dp[j - 1]);
                dp[j] += grid[i][j];
            }
        }
        return dp[n - 1];
    }

    int differenceOfSum(vector<int>& nums) {
        int elementSum = 0, digitSum = 0;
        for (int num : nums)
        {
            elementSum += num;
            while (num > 0)
            {
                digitSum += num % 10;
                num /= 10;
            }
        }
        return elementSum - digitSum;
    }

    int left = 0, right = 0, num;
    string path;
    vector<string> ret;
    void dfs()
    {
        if (right == num)
        {
            ret.push_back(path);
            return;
        }
        if (left < num)
        {
            path += '(', ++left;
            dfs();
            path.pop_back(), --left;
        }
        if (left > right)
        {
            path += ')', ++right;
            dfs();
            path.pop_back(), --right;
        }
    }
    vector<string> generateParenthesis(int n) {
        num = n;
        dfs();
        return ret;
    }

    void qsort(vector<int>& nums, int left, int right)
    {
        if (left >= right) return;
        int num = getKey(nums, left, right);
        int cur = left, begin = left - 1, end = right + 1;
        while (cur < end)
        {
            if (nums[cur] < num) swap(nums[cur++], nums[++begin]);
            else if (nums[cur] == num) ++cur;
            else swap(nums[--end], nums[cur]);
        }
        qsort(nums, left, begin);
        qsort(nums, end, right);
    }

    int getKey(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }

    vector<int> sortArray(vector<int>& nums) {
        srand(time(NULL));
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }
};

int main()
{
    Solution s;
    vector<int > v= {5, 3, 2, 1};
    s.sortArray(v);
}